package com.shiguiwu.springmybatis.algorithm.tree;

import lombok.Data;

/**
 * @description: 二叉排序树
 * @author: stone
 * @date: Created by 2021/5/30 14:40
 * @version: 1.0.0
 * @pakeage: com.shiguiwu.springmybatis.algorithm.tree
 *
 * 删除叶子节点
 * (1) 需先去找到要删除的结点 targetNode
 * (2) 找到targetNode 的 父结点 parent
 * (3) 确定 targetNode 是 parent的左子结点 还是右子结点
 * (4) 根据前面的情况来对应删除
 * 左子结点 parent.left = null
 * 右子结点 parent.right = null
 * 删除只有一颗子树的节点
 * (1) 需先去找到要删除的结点 targetNode
 * (2) 找到targetNode 的 父结点 parent
 * (3) 确定targetNode 的子结点是左子结点还是右子结点
 * (4) targetNode 是 parent 的左子结点还是右子结点
 * (5) 如果targetNode 有左子结点
 * 5-1 如果 targetNode 是 parent 的左子结点
 * parent.left = targetNode.left;
 * 5-2 如果 targetNode 是 parent 的右子结点
 * parent.right = targetNode.left;
 * (6) 如果targetNode 有右子结点
 * 6-1 如果 targetNode 是 parent 的左子结点
 * parent.left = targetNode.right;
 * 6-2 如果 targetNode 是 parent 的右子结点
 * parent.right = targetNode.right
 * 删除两个子树节点
 * (1) 需先去找到要删除的结点 targetNode
 * (2) 找到targetNode 的 父结点 parent
 * (3) 从targetNode 的右子树找到最小的结点
 * 注：若处理的是左子树，则找到最大的节点
 * (4) 用一个临时变量，将 最小结点的值保存 temp = 11
 * (5) 删除该最小结点
 * (6) targetNode.value = temp
 *
 */
public class BinarySortTree {

    private Node root;

    public BinarySortTree(Node root) {
        this.root = root;
    }

    public void delete(int value) {
        //1,是空，直接返回
        if (root == null) {
            return;
        }
        //2,删除的root节点
        if (root.left == null && root.right == null) {
            root = null;
            return;
        }

        //3,找寻要删除的节点
        Node targetNode = root.search(value);
        if (null == targetNode) {
            return;
        }

        //不是空，则找到他的父节点
        Node parentNode = root.searchParent(value);

        //a,删除的是叶子节点
        if (targetNode.left == null && targetNode.right == null) {
            if (parentNode.right != null && parentNode.right.val == value) {
                parentNode.right = null;
            }
            if (parentNode.left != null && parentNode.left.val == value) {
                parentNode.left = null;
            }

        }

        //b,删除有两颗子数的节点 todo
        else if (targetNode.left != null && targetNode.right != null) {

        }

        //c,删除有一颗子树的节点
        else {
            //待删除的节点有左子节点
            if (targetNode.left != null ) {
                //目标节点的子节点是左子节点
                if (targetNode.val == parentNode.left.val) {
                    parentNode.left = targetNode.left;
                }
                //目标节点的子节点是右子节点
                else {
                    parentNode.right = targetNode.left;
                }
            }

            //待删除的节点是有柚子节点
            else {
                //目标节点的子节点是左子节点
                if (targetNode.val == parentNode.right.val) {
                    parentNode.left = targetNode.right;
                }
                //目标节点的子节点是右子节点
                else {
                    parentNode.right = targetNode.right;
                }
            }
        }

    }


    @Data
    public static class Node {
        private int val;


        private Node left;

        private Node right;

        public Node(int val) {
            this.val = val;
        }


        /**
         * 查找父节点
         *
         * @param value
         * @return
         */
        public Node searchParent(int value) {
            if (this.left != null && this.left.val == value
                    || (this.right != null && this.right.val == value)) {
                return this;
            } else {
                if (value > this.val && this.right != null) {
                    return this.right.searchParent(value);
                }
                //左边
                else if (value <= this.val && this.left != null) {
                    return this.left.searchParent(value);
                }
                //否则

                else {
                    return null;
                }
            }

        }


        /**
         * 根据值查询node节点
         *
         * @param val 待查找的值
         * @return 查询节点, 没有找到返回空
         */
        public Node search(int val) {
            if (this.val == val) {
                return this;
            } else if (this.val > val) {
                if (this.left == null) {
                    return null;
                }
                return this.left.search(val);
            } else {
                if (this.right == null) {
                    return null;
                }

                return this.right.search(val);
            }


        }


        /**
         * 添加节点
         *
         * @param node 待添加节点
         */
        public void add(Node node) {
            if (null == node) {
                return;
            }

            if (this.val > node.val) {
                if (this.left == null) {
                    this.left = node;
                } else {
                    this.left.add(node);

                }
            }
            // this.val <= node.val
            else {
                if (this.right == null) {
                    this.right = node;
                } else {
                    this.right.add(node);

                }
            }

        }


    }
}


